package zuoshen_video2.dynamic;

import java.util.Arrays;

import org.junit.Test;

/* 
    9 * 10 的象棋棋盘，马位于(0,0)点
    现在想要马跳到(m, n), 且一定跳k步，求方案数
    马走日字型。(x +- 2, y +- 1) (x +- 1, y +- 2)
*/
public class HouseJump {

    public int jump(int m, int n, int k) {
        return dfs1(0, 0, k, m, n);
    }

    int[] p1 = { -1, +1 }, p2 = { -2, +2 };

    public int dfs1(int x, int y, int m, int n, int s) {
        if (x < 0 || y < 0 || x >= 9 || y >= 10)
            return 0;
        if (s == 0)
            return x == m && y == n ? 1 : 0;
        int res = 0;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                res += dfs1(x + p1[i], y + p2[j], m, n, s - 1);
                res += dfs1(x + p2[i], y + p1[j], m, n, s - 1);
            }
        }
        return res;
    }

    @Test
    public void test1() {
        System.out.println(jump(7,7,10));
    }

    int[][][] f;
    public int jump2(int m, int n, int l) {
        if (m >= 9 || n >= 10)
            return 0;
        int[][][] f = new int[9][10][l + 1];
        // 初始化：f[i][j][0] 除了 f[m][n]全部为0
        f[m][n][0] = 1;

        this.f = f;
        for (int k = 1; k <= l; k++) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 10; j++) {
                    // 刚开始默认为0
                    f[i][j][k] += getValue(i + 1, j - 2, k - 1);
                    f[i][j][k] += getValue(i + 1, j + 2, k - 1);
                    f[i][j][k] += getValue(i + 2, j + 1, k - 1);
                    f[i][j][k] += getValue(i + 2, j - 1, k - 1);
                    f[i][j][k] += getValue(i - 1, j - 2, k - 1);
                    f[i][j][k] += getValue(i - 1, j + 2, k - 1);
                    f[i][j][k] += getValue(i - 2, j + 1, k - 1);
                    f[i][j][k] += getValue(i - 2, j - 1, k - 1);

                }
            }
        }
        // System.out.println(Arrays.deepToString(f));
        return f[0][0][l];
    }

    public int getValue(int x, int y, int k) {
        if (x <0 || y < 0 || x >= 9 || y >= 10) return 0;
        return f[x][y][k];
    }

    @Test
    public void test2() {
        System.out.println(jump2(7,7,10));
    }
}
